package com.heima.leetcode.datastructure.priorityqueue;

import com.heima.leetcode.datastructure.linkedlist.ListNode;

/**
 * 存放ListNode的优先级队列，基于小顶堆实现
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/3 20:25
 */
public class ListNodePriorityQueue {
    private final ListNode[] arr;
    private int size;

    public ListNodePriorityQueue(int capacity) {
        arr = new ListNode[capacity];
    }

    public boolean offer(ListNode node){
        if (isFull()){
            return false;
        }
        int child = size;
        int parent = (size - 1) >> 1;
        while (child > 0 && arr[parent].val > node.val){ // 根节点没有父节点
            arr[child] = arr[parent];
            child = parent;
            parent = (child - 1) >> 1;
        }
        arr[child] = node;
        size++;
        return true;
    }

    public ListNode poll(){
        if (isEmpty()){
            return null;
        }
        swap(0,size - 1);
        ListNode node = arr[--size];
        arr[size] = null;
        down(0);
        return node;
    }

    private void down(int root) {
        int left = root * 2 + 1;
        int right = left + 1;
        int min = min(root,left,right);
        if (min == root){
            return;
        }
        swap(root,min);
        down(min);
    }

    private int min(int root, int left, int right) {
        if (left >= size){
            return root;
        }
        if (right == size){
            return arr[root].val <= arr[left].val ? root : left;
        }
        if (arr[root].val <= arr[left].val){
            return arr[root].val <= arr[right].val ? root : right;
        }
        return arr[left].val < arr[right].val ? left : right;
    }

    private void swap(int index1, int index2){
        ListNode temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public boolean isFull(){
        return size == arr.length;
    }
}
